In [2]:
def calc_pascal_triangle(lines, start=None):
'''
Function to compute Pascal's triangle for a given number
of lines.
Returns a list of lists containg the lines of pascal's
triangle.
>>> pascal_triangle(-1)
Traceback (most recent call last):
...
AssertionError: Input is less than zero
>>> pascal_triangle(0)
Traceback (most recent call last):
...
AssertionError: Input is less than zero
>>> calc_pascal_triangle(1)
[[1]]
>>> calc_pascal_triangle(3)
[[1], [1, 1], [1, 2, 1]]
'''
assert type(lines) == int, 'Input is not an integer'
assert lines > 0, 'Input is less than zero'
if start == None:
start = [[1]]
if lines == 1:
return start
elif lines > 1:
prev = start[-1]
new = [1] + [sum(i) for i in zip(prev, prev[1:])] + [1]
return calc_pascal_triangle(lines-1, start + [new])
def pascal_triangle(lines, file=None):
'''
Wrapper function to print Pascal's triangle to a file or stdout.
>>> pascal_triangle(3)
1
1 1
1 2 1
>>> pascal_triangle(3, 'test.txt')
'''
triangle = calc_pascal_triangle(lines)
# Calculate space needed for line and numbers
num_width = len(str(max(triangle[-1])))
if num_width % 2 == 0:
num_width += 1
# Calculate needed line width
line_width = num_width*lines+lines-1
# Line skeletton for formatting
line_ske = '{:^' + str(line_width) + '}'
# Number skeletton for formatting
num_ske = '{:^'+ str(num_width) +'}'
if file:
with open(file,'w') as f:
for line in triangle:
line = [num_ske.format(x) for x in line]
line = ' '.join(line)
f.write(line_ske.format(str(line)) + '\n')
else:
for line in triangle:
line = [num_ske.format(x) for x in line]
line = ' '.join(line)
print(line_ske.format(str(line)))
if __name__ == '__main__':
import doctest
doctest.testmod()
In [3]:
# 14 lines of Pascal's Triangle
pascal_triangle(14)
In [33]:
def seaveEra(limit):
'''
A function implementing the sieve of erathostenes.
It takes an upper limit and yields all prime numbers
under this limit.
>>> list(seaveEra(7))
[2, 3, 5]
'''
status = [True] * limit
status[0] = status[1] = False
for (i, isprime) in enumerate(status):
if isprime:
yield i
for n in range(i*i, limit, i):
status[n] = False
def factorize(num, primes=None):
'''
This function takes an integer and returns a dict
of prime factors.
>>> factorize(1)
Traceback (most recent call last):
...
AssertionError: Input is smaller than 2
>>> factorize(7)
{7: 1}
'''
import math
assert type(num) == int, 'Input is not an integer'
assert num >= 2, 'Input is smaller than 2'
if primes == None:
primes = list(seaveEra(int(math.sqrt(num))+2))
result = {}
for x in primes:
if num % x == 0:
result[x] = 1
num = num // x
while num % x == 0:
result[x] += 1
num = num // x
#if result == {}:
# raise ValueError(' c')
if num == 1:
return result
if (max(primes)+1)**2 > num:
result = {num: 1}
return result
else:
mes = ('At leat one prime factor '
'is bigger than {}')
return mes.format(max(primes))
if __name__ == '__main__':
import doctest
doctest.testmod()
In [34]:
# Test the factorize function. A precomputed list of primes is used.
factorize_tests = [1231, 123259, 12345577, 1234567811, 112233445589,
11223344556607, 4, 1001, 198473094, 13918452024,
32574985749857]
primes = list(seaveEra(10000000))
for num in sorted(factorize_tests):
print('{:15} {}'.format(num, factorize(num, primes)))
In [6]:
import time
from functools import wraps
def timeit(func):
'''
Decorator to time the execution time of a function
'''
@wraps(func)
def timed(*args):
start = time.perf_counter()
result = func(*args)
total = time.perf_counter() - start
return result, total
return timed
In [7]:
# Time the factorization function.
factorize_tests2 = [4,1001,1231,123259,198473094]
timed_factorize = timeit(factorize)
for num in factorize_tests2:
print('{:15} {}'.format(num, timed_factorize(num)[1]))
In [8]:
def multiply_polynoms(polyA, polyB):
'''
This fuction takes two lists as parameters which represent polynoms.
It returns the product of those two polynomes.
'''
result = [0]*(len(polyA)+len(polyB)-1)
for i in range(len(polyA)):
for j in range(len(polyB)):
result[i+j] += polyA[i]*polyB[j]
return result
In [9]:
#Time the multiply_polynoms function
timed_multiply_polynoms = timeit(multiply_polynoms)
x = []
y = []
for i in range(0,2001, 100):
poly = i*[1]
x.append(i)
calls = []
for i in range(5):
calls.append(timed_multiply_polynoms(poly, poly)[1])
y.append(sum(calls)/len(calls))
In [10]:
# Plot the mean execution time against the polynom length
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(x,y)
plt.plot(x, [0.0000002*x**2 for x in x],'--')
Out[10]:
The polynom multiplication is in $\mathcal{O}(n^2)$. You can see this in the plot as well as in the fact that two loops are part of the calculation.